package org.hot100.h146;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author yu
 * @Date 2022/8/6
 */
public class LRUCache3 {

    public static void main(String[] args) {

    }

    Map<Integer, Node3> map;
    DoubleList3 doubleList;
    int cap;

    public LRUCache3(int size) {
        this.map = new HashMap<>();
        this.doubleList = new DoubleList3();
        this.cap = size;
    }

    public int get(int k) {
        if (map.containsKey(k)) {
            int val = map.get(k).v;
            put(k, val);
            return val;
        }
        return -1;
    }

    public void put(int k, int v) {
        Node3 node3 = new Node3(k, v);
        if (map.containsKey(k)) {
            doubleList.remove(map.get(k));
        } else {
            if (cap == doubleList.getSize()) {
                Node3 last = doubleList.removeLast();
                map.remove(last.k);
            }
        }
        doubleList.addFirst(node3);
        map.put(k, node3);
    }
}

class DoubleList3 {

    int size;
    Node3 head;
    Node3 tail;

    public void addFirst(Node3 node3) {
        if (head == null && tail == null) {
            head = tail = node3;
        } else {
            Node3 n = head;
            node3.next = n;
            n.prev = node3;
            head = node3;
        }
        size++;
    }

    public void remove(Node3 node3) {
        if (head == node3 && tail == node3) {
            head = tail =null;
        }
        if (head == node3) {
            node3.next.prev = null;
            head = node3.next;
        }
        if (tail == node3) {
            node3.prev.next = null;
            tail = node3.prev;
        }
        if (head != node3 && tail != node3) {
            node3.prev.next = node3.next;
            node3.next.prev = node3.prev;
        }
        size--;
    }

    public Node3 removeLast() {
        Node3 temp = tail;
        remove(tail);
        return temp;
    }

    public int getSize() {
        return this.size;
    }

}

class Node3 {

    int k;
    int v;
    Node3 prev;
    Node3 next;

    public Node3(int k, int v) {
        this.k = k;
        this.v = v;
    }
}